package 图.并查集;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/15 22:15
 */
public class lc684冗余连接 {

    /*
     简而言之 : 就是 将 x y 进行 union(连通的时候) 先去 判断 x y 是否 已经连通, 如果 x y 已经连通, 那么此次 union 将会产生环
     画个图 ,表示一下就明白了!
     */
    public int[] solve(int[][] edges) {
        int n = edges.length;
        UF uf = new UF(n);
        int ans[] = null;
        for (int[] edge : edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])){
                ans = new int[]{edge[0],edge[1]};
                break;
            }
            uf.union(edge[0],edge[1]);
        }
        return ans;
    }


    static class UF {
        int parent[];
        int size[]; // 该题 用不到 size 数组
        int sets;

        public UF(int n) {
            parent = new int[n + 1];
            sets = n;
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            return parent[x] = find(parent[x]);
        }

        public void union(int i, int j) {
            int ip = find(i), jp = find(j);
            if (ip != jp) {
                parent[ip] = jp;
//                size[jp] += size[ip];
                sets--;
            }
        }
    }
}
